package com.liang.bishi.tc;

import java.util.Scanner;

/**
 * 9.24 同程旅游笔试第一题
 * 构造一个大小为n的数组，使奇数位置元素为奇数、偶数位置元素为偶数，且每个元素在 [1, m] 内（可重复使用）
 * 问有多少种不同方案？答案对(10^9+7)取模。
 * <p>
 * 3 3
 * 4
 */
public class Problem1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 构造的数组大小
        int n = in.nextInt();
        // 1 到 m 个整数
        int m = in.nextInt();
        System.out.println(getAnswer(n, m));
    }

    private static final long MOD = (long) 1e9 + 7;

    // 3 3 [1,2,3]、[3,2,1]、[1 2 1]、[3 2 3]  1 2 3 4
    // 4 3 [1 2 3 2] [1 2 1 2] [3 2 1 2] [3 2 3 2]
    public static long getAnswer(int n, int m) {
        // 奇数个数
        long oddCount = (m + 1) / 2;
        // 偶数个数
        long evenCount = m / 2;
        // 遍历奇数位置
        for (int i = 1; i < (n + 1) / 2; i++) {
            oddCount = (oddCount * oddCount) % MOD;
        }
        // 遍历偶数位置
        for (int i = 1; i < n / 2; i++) {
            evenCount = (evenCount * evenCount) % MOD;
        }
        return (oddCount * evenCount) % MOD;
    }

}
